perm filename GEOMED.BGB[S,DOC] blob
sn#500357 filedate 1981-09-10 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00015 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 TITLE PAGE & CONTENTS. MARCH 1975
C00006 00003 1.0 INTRODUCTION TO GEOMEL, GEOMES and MESGEM.
C00010 00004 1.1 GEOMES Primer - Geometric Modeling Embedded in SAIL.
C00014 00005
C00017 00006 1.2 MESGEM PRIMER. Message Procedure Geometric Modeling.
C00018 00007 1.3 GEOMEL PRIMER. Geometric Modeling Embedded in LISP.
C00019 00008 2.0 MEMORY, CONTROL, INPUT AND OUTPUT ROUTINES.
C00022 00009 3.0 DATUM AND LINK NAMES.
C00024 00010 4.0 WINGED EDGE PRIMITIVES.
C00028 00011 4.0 EULER MAKE PRIMITIVES.
C00030 00012 5.0 EULER KILL PRIMITIVES.
C00033 00013 6.0 EUCLIDEAN TRANSFORMATIONS.
C00037 00014 7.0 IMAGE FORMING ROUTINES.
C00040 00015 9.0 Description of GEOMED Source Code.
C00043 ENDMK
C⊗;
TITLE PAGE & CONTENTS. MARCH 1975
GEOMED REFERENCE MANUAL
BRUCE G. BAUMGART
ABSTRACT: The subroutines under GEOMED are presented as a modeling
system accessible from LISP, SAIL and SAIL message procedures.
_______________________________________________________________________________
1.0 Introduction to GEOMEL, GEOMES, MESGEM and CRE.
1.1 GEOMES PRIMER. Geometric Modeling Embedded in SAIL.
1.2 MESGEM PRIMER. Message Procedure Geometric Modeling.
1.3 GEOMEL PRIMER. Geometric Modeling Embedded in LISP.
2.0 Memory, Control, Input and Output Routines.
GEOMED MKUNIV MKNODE KLNODE
MKWORLD MKCAMERA MKWINDOW
OUTB3D OUTGEM OUTCAM OUTVID PLOTO
INB3D INGEM INCAM INCRE
3.0 Datum and Link Names:
XWC YWC ZWC AA BB CC XPP YPP ZPP
IX IY IZ JX JY JZ KX KY KZ
NFACE PFACE NED PED NVT PVT DAD SON BRO SIS
ALT ALT2 CW CCW CAR8 CDR8
4.0 Winged Edged Primitives:
MKB MKF MKE MKV MKFRAME
WING INVERT EVERT
ECW ECCW OTHER VCW VCCW FCW FCCW
BDET BATT BGET
5.0 Euler Routines:
MKBFV MKEV ESPLIT MKFE GLUEE
KLBFEV KLFE KLEV UNGLUE
GLUE MKCOPY SWEEP ROTCOM PYRAMID FVDUAL
MKCUBE MKCYLN MKBALL
BIN BUN BSUB MKCVEX
MKBUCK ECUT FCUT BCUT
6.0 Euclidean Routines:
TRANSL ROTATE SHRINK APTRAM INTRAM DISTANCE
NORM MKROT1 ORTHO1 ORTHO2 DETERM ANGL3V
7.0 Image Forming Routines:
GEODPY IIIDPY SHOW1 SHOW2 SHOW3 SHOW4
TAKE1 TAKE2 OCCULT SHADOW CLIPER
VPROJ UNPROJ FACOEF ECOEF
8.0 Arithmetic and Display Routines:
PI SQRT LOG SIN COS ATAN ATAN2 ASIN ACOS
DPYBUF DPYSST DPYSET DPYBIG DPYBRT
AVECT AIVECT RVECT RIVECT DPYOUT
9.0 Description of GEOMED Source Code.
1.0 INTRODUCTION TO GEOMEL, GEOMES and MESGEM.
GEOMED is implemented in PDP-10 machine code and is composed
of about 250 subroutines. These subroutines are SAIL and LISP
accessible. When load in a SAIL core image, the GEOMED subroutines
are called GEOMES for "Geometric Modeling Embedded in SAIL"; when
loaded with LISP, they are referred to as GEOMEL, "Geometric Modeling
Embedded in LISP". Strictly defined, the name "GEOMED" refers to the
interactive editor itself; however the reader is warned that the
named "GEOMED" may also refer to GEOMEL, GEOMES, MESGEM, the data
structures, the command languages, and so on.
As a graphics language, GEOMED is all semantics with no
syntax of its own. The subroutines take from one to four arguments,
return one or no values, and usually have considerable side effects
on the data structures. Unless otherwise noted, all arguments and
values are integers; subroutines executed only for effect tend to
return integer value zero.
The GEOMED data structure is implemented as twelve word
blocks containing pointers and data in the fashion usual to graphics
and simulation. The twelve word blocks are called "nodes". Nodes are
referred to by their actual machine address in the user core image,
which is an integer called a "link". Subroutines that take nodes as
arguments or return nodes as values pass links rather than the nodes
themselves. In SAIL, the user core image can be accessed as a
special array named MEMORY; in LISP, the core image is accessible
in the last resort by the SUBRs: EXAMINE and DEPOSIT.
*********************************************************************
NOTE: The use of GEOMED interactively is not documented
online except inside the program itself. Type "?" to it, followed by
any character to find out what that character does. Type H to see
more complete documentation. One operation of particular interest
that has become easier subsequent to the writing of GEOMED is that of
getting the GEOMED display into a set of vectors for the POX document
compiler (or any other processor that accepts XY-coordinate vectors).
To do this, use the P command of GEOMED, then run the resulting plot
file through the IIIPOX program.
1.1 GEOMES Primer - Geometric Modeling Embedded in SAIL.
The example GEOMES program, immediately below, creates
two cubic prisms and displays them rotating. The header file,
GEOMES.HDR, is kept on the disk area [GEM,HE] and contains the names
of the necessary load modules, the declarations of all the modeling
routines and SAIL macros for accessing GEOMED data structures. I
would strongly advise the user to study a copy of the header for it
is the most accurate index of the modeling routines.
After the header, the first routine to execute must be MKUNIV
(make universe), which initialize the modeling data structures. In
the example, two blocks are created using the MKCUBE routine which
takes three arguments: width, breadth and height of a rectangular
parallelepiped. All creation routines return an integer which is the
absolute machine address of the GEOMED node of the entity created.
(GEOMED data structures have absolutely nothing to do with LEAP).
The next routine used is GEODPY which refreshs the display of
the model using the default parameters or GEOMED. (See SHOW1 and
SHOW2 for more flexible display refresh routines). Finally, the
example calls TRANSL and ROTATE which perform the the Euclidean
transformations translation and rotation. TRANSL takes four argument:
first the thing to be moved followed by the three components of a
translation vector; similarly ROTATE takes four arguments: first the
thing to be moved followed by the three components of a rotation
vector.
-------------------------------------------------------------------------------
BEGIN "EXAMPLE1"
REQUIRE "GEOMES.HDR[GEM,HE]" SOURCE_FILE;
DEFINE π="3.1415927";
INTEGER B1,B2;
MKUNIV;
B1 ← MKCUBE(2,4,8);
B2 ← MKCUBE(1,2,4);
TRANSL(B2,-2,2,0);
WHILE TRUE DO
BEGIN
GEODPY;
ROTATE(B1,π/10,π/12,π/13);
ROTATE(B2,-π/14,π/16,-π/17);
END;
END "EXAMPLE1";
-------------------------------------------------------------------------------
In example #2, immediately below, the
model of a mechanical arm is read in and the first three joints are run
through a simulated arm motion. The routine INB3D reads B3D
polyhedra files. The FDNAME, find name, routine searchs for GEOMED
body print names, FDNAME returns zero when a name is not found. The
routine INCAM reads in a camera file. Finally, the routine SHOW2
calls the hidden line eliminator; leaving the SHOW2 arguments zero
causes default parameters to be used.
-------------------------------------------------------------------------------
BEGIN "EXAMPLE2"
REQUIRE "GEOMES.HDR" SOURCE_FILE;
DEFINE α="COMMENT";
INTEGER B1,B2,J1,J2,J3,J4,J5,J6,C1,CHR,I;
MKUNIV;GEODPY;
B1 ← INB3D("ARM[DAT,BGB]"); α MODEL OF THE YELLOW ARM;
J1 ← FDNAME("JOINT1"); α SHOULDER - ABOUT VERTICAL;
J2 ← FDNAME("JOINT2"); α ARM - ABOUT HORIZONTAL;
J3 ← FDNAME("JOINT3"); α SLIDE;
J4 ← FDNAME("JOINT4"); α WRIST TWIST;
J5 ← FDNAME("JOINT5"); α WRIST FLAP;
J6 ← FDNAME("JOINT6"); α HAND
C1 ← INCAM("ARMCAM[DAT,BGB]");
SHOW2(0,0); α HIDDEN LINE ELIMINATION;
FOR I←0 STEP 1 UNTIL 70 DO
BEGIN
ROTATE(-J1,0,0,π/18);
ROTATE(-J2,0,0,π/20);
TRANSL(-J3,0,0,0.1);
SHOW2(0,0);
END;
END "EXAMPLE2"
-------------------------------------------------------------------------------
1.2 MESGEM PRIMER. Message Procedure Geometric Modeling.
The message procedure modeling routines are declared by the
source file MESGEM.HDR[GEM,HE] which should be used in place of
GEOMES.HDR[GEM,HE]. Almost all the subroutine and link names of
MESGEM are the same as in GEOMES, however the user will have to load
his program with SYS:GLBLOW.
1.3 GEOMEL PRIMER. Geometric Modeling Embedded in LISP.
A dump version of GEOMEL is available on [GEM,HE] and the
LISP is a current version UCI LISP.
GEOMEL is created from IL by loading the REL files GEOMED, GEOMEL,
UTILTY, EULER, EUCLID, OCCULT and BIN
from [GEM,HE]
and by EVAL'ing (INC(INPUT (GEM HE) (GEOMEL.LSP)))
2.0 MEMORY, CONTROL, INPUT AND OUTPUT ROUTINES.
SAIL:
top-of-stack ← GEOMED; Geometric Editor.
univer ← MKUNIV; Make universe, initialization.
node ← MKNODE(word0); Make node with given type bits.
KLNODE(QNODE); Kill node.
LISP:
(GEOMED) Geometric Editor returns top-of-stack.
(MKUNIV) Make universe, returns universe pointer.
(MKNODE word0) Make node with given type bits, returns node.
(KLNODE QNODE) Kill node, returns 0.
The routine named GEOMED, passes control to the geometric
editor, which enters the jump table command scanner described in the
A.I. memo #232. When the exit command "εE" is given, GEOMED returns
the the address of the node which is at the top of its stack (or
zero, if the stack is empty). MKUNIV; initializes GEOMED node
space. QNODE ← MKNODE(Q); takes a node from the empty node list;
memory space is requested from SAIL or LISP as needed. The integer Q
is stored in the TYPE bits (word zero) of the newly created node.
KLNODE(QNODE); returns a node to the empty node list.
SAIL: LISP:
OUTB3D(filename,body); (OUTB3D filename body)
OUTGEM(filename,body); (OUTGEM filename body)
OUTCAM(filename); (OUTCAM filename)
OUTV2D(filename); (OUTV2D filename)
SAIL: LISP:
body ← INB3D(filename); (INB3D filename)
body ← INGEM(filename); (INGEM filename)
camr ← INCAM(filename); (INCAM filename)
body ← INCRE(filename); (INCRE filename)
3.0 DATUM AND LINK NAMES.
Datum names: XWC YWC ZWC World Coordinates Locus.
XPP YPP ZPP Perspective Projected Locus.
AA BB CC KK Face or Edge Coefficients.
IX IY IZ I-unit vector of a frame.
JX JY JZ J-unit vector of a frame.
KX KY KZ K-unit vector of a frame.
The above datum names all refer to real numbers. In GEOMES,
the datum names are defined as MEMORY array references and so can
appear on the left of a left arrow. In GEOMEL, eighteen
corresponding datum store routines are provided; for example:
(XWC$ xvalue vertex), will store a new X coordinate value into a
vertex node.
Link names: NFACE PFACE Face Ring.
NED PED Edge Ring.
NVT PVT Vertex Ring.
DAD SON Parts Tree Links.
BRO SIS Parts Tree Links.
ALT ALT2 GEOMED Temporaries.
CW CCW Body ring of world.
NLINK PLINK User Links.
TRAM Tram nodes.
In both GEOMES and GEOMEL, the links may be modified by the
two argument subroutines of the same name with a period "$" suffixed.
For example, PLINK$(Q,E) will place the link (or integer value) Q
into the ALT halfword link position of the node E.
4.0 WINGED EDGE PRIMITIVES.
4.1 NODE MAKERS.
SAIL: body ← MKB(world); LISP: (MKB world)
face ← MKF(body); (MKF body)
edge ← MKE(body); (MKE body)
vert ← MKV(body); (MKV body)
tram ← MKTRAM; (MKTRAM)
MKB makes a body node and place it in the body ring of the
given world (or in the now world if the given world argument is
zero). MKF, MKE and MKV make a face, edge or vertex node respectively
and place it in the proper given body's face, edge or vertex ring.
MKTRAM simply returns a tram node with a unit rotation matrix and
zero world locus.
4.2 WING LINK MUNGING.
SAIL: WING(edge1,edge2); LISP: (WING edge1 edge2)
INVERT(edge); (INVERT edge)
EVERT(body); (EVERT body)
Given that each edge has its proper two vertices and two
faces, WING(E1,E2) will make the edges point at each other in the
correct orientation. INVERT(edge) will flip the linear orientation of
an edge. EVERT(body) will flip the surface orientation of a body,
making solids into holes and vise versa.
4.3 FACE AND VERTEX PERIMETER ACCESSING.
next cw edge ← ECW(edge,face or vertex);
next ccw edge ← ECCW(edge,face or vertex);
cw vertex ← VCW(edge,face);
ccw vertex ← VCCW(edge,face);
cw face ← FCW(edge,vertex);
ccw face ← FCCW(edge,vertex);
face or vertex ← OTHER(edge,face or vertex);
ECW(E,FV) and ECCW(E,FV) fetch the next edge clockwise or
counter clockwise from the given edge about the given face or vertex.
VCW(edge,face) and VCCW(edge,face) fetch the next vertex clockwise or
counter clockwise from the given edge with repect to the given face.
FCW(edge,vertex) and FCCW(edge,vertex) fetch the next face clockwise
or counter clockwise from the given edge with repect to the given
vertex. The OTHER(<edge>,<face|vertex>) will fetch the face or vertex
of the given edge which is not equal to the given face or vertex.
4.3 PARTS TREE AND BODY GET.
BDET(body);
BATT(body1,body2);
body ← BGET(face or edge or vertex);
BDET(body) will detach a body from the parts tree.
4.0 EULER MAKE PRIMITIVES.
4.1 BNEW ← MKBFV; Make vertex polyhedron.
4.2 VNEW ← MKEV(F,V); MAKES NEW EDGE AND VERTEX SUCH THAT:
VNEW = NVT(ENEW); V = PVT(ENEW);
VNEW ← ESPLIT(E); MAKES NEW EDGE AND VERTEX...
4.3 ENEW ← MKFE(V1,F,V2); MAKES NEW FACE AND EDGE SUCH THAT:
FNEW = NFACE(ENEW); F = PFACE(ENEW);
V1 = PVT(ENEW); V2 = NVT(ENEW).
4.4 ENEW ← GLUEE(F1,V1,F2,V2); MAKES NEW EDGE, KILLS F2,
AND MAKES A HOLE OR KILLS A BODY.
V1 = PVT(ENEW); V2 = NVT(ENEW).
4.2 VNEW ← MKEV(FACE,VERTEX);
VNEW ← ESPLIT(EDGE);
Make a new edge and a new vertex in the given FACE from the
given VERTEX; the new vertex is return, VNEW; the new edge can be
accessed by taking PED(VNEW).
ESPLIT, makes a new edge and a new vertex, VNEW; the new edge may be
obtained by taking PED(VNEW); the new edge is place between VNEW and
PVT(EDGE).
4.3 ENEW ← MKFE(V1,FACE,V2);
Make a new face and a new edge by joining V1 and V2 of FACE.
The new edge is returned, ENEW; the new face may always be obtained
by taking NFACE(ENEW).
5.0 EULER KILL PRIMITIVES.
5.1 QNEW ← KLBFEV(Q); Kill entity.
5.2 F ← KLFE(E); Kill E and NFACE(E), return PFACE(E).
5.3 E ← KLEV(V); Kill V and PED(V), return other E of V.
V ← KLEV(E); Kill E and NVT(E), retirn PVT(E).
5.4 FNEW ← UNGLUE(E); Undo an GLUEE.
.....................................................................
6.0 EASY POLYHEDRON ROUTINES.
body ← GLUE(face1,face2); Glue face-face.
qnew ← MKCOPY(entity); Make copy.
face ← SWEEP(face,flag); Sweep cylinder.
face ← ROTCOM(face); Rotation completion.
peak ← PYRAMID(fv); Make pyramid on a face (or vertex).
body ← FVDUAL(body); Make face/vertex dual of a body.
bnew ← MKCUBE(dx,dy,dz); Make right rectangular prism.
bnew ← MKCYLN(radius,n,dz); Make right cylinder.
bnew ← MKBALL(radius,m,n; Make sphere approximation.
MKCUBE(dx,dy,dz) creates and returns a cubic right prism.
MKCYLN(r,n,z) creates and returns a regular N-sided right prism.
bnew ← BIN(body1,body2); Body intersection.
bnew ← BUN(body1,body2); Body union.
bnew ← BSUB(body1,body2); Body subtraction.
MKCVEX(body or face); Make convex faces.
6.0 EUCLIDEAN TRANSFORMATIONS.
Euclidean Transformations with respect to world frame:
TRANSL(object,dx,dy,dz);
ROTATE(object,wx,wy,wz);
SHRINK(object,sx,sy,sz);
Euclidean Transformations with respect to objects own frame:
TRANSL(-object,dx,dy,dz);
ROTATE(-object,wx,wy,wz);
SHRINK(-object,sx,sy,sz);
Euclidean Transformations with respect to arbitrary frame:
TRANSL(XWD(frame,object),dx,dy,dz);
ROTATE(XWD(frame,object),wx,wy,wz);
SHRINK(XWD(frame,object),sx,sy,sZ);
Make Euclidean Transformation
tran ← TRANSL(0,dx,dy,dz);
tran ← ROTATE(0,wx,wy,wz);
tran ← SHRINK(0,sx,sy,sz);
OBJECT ← APTRAN(OBJECT,TRAN);
FRAME ← INTRAN(FRAME);
Z ← DISTANCE(BFEV1,BFEV2);
NORM
MKROT1
ORTHO1(FRAME)
ORTHO2(FRAME)
Z ← DETERM(FRAME)
ANGL3V(V1,V2,V3)
7.0 EUCLIDEAN TRANSFORMATIONS.
When the ENTITY argument is non-zero, these subroutines
perform the indicated Euclidean Transformation: translation,
rotation, dilation and reflection. When the ENTITY argument is ZERO,
then a FRAME node representing the desired transformation is
returned.
FRAMES and EUCLIDEAN TRANSFORMATIONS
A frame node has two intrepretations: it may be used to
represent a frame of reference or it may be used to specify a
Euclidean transformation.
As a frame of reference the XWC, YWC, ZWC datums contain the
location of the origin of the frame in world coordinates; and the
remaining nine datums IX,IY,IZ, JX,JY,JZ, KX,KY,KZ are the components
of three unit vectors I, J, and K that determine a right handed
rectangular Cartesian coordinate system. The nine components of the
unit vectors form an orthonormal rotation matrix.
As a Euclidean transformation, the frame is applied to the
3-D world coordinates of an entity Q to make new coordinates.
---------------------------------------------------------------------
| APTRAN's inner most subroutine. |
| Expects arguments in V and Q. Clobbers 1,2,X,Y,Z. |
| |
| X ← XWC(V); |
| Y ← YWC(V); |
| Z ← ZWC(V); |
| |
| XWC(V) ← X*IX(Q) + Y*JX(Q) + Z*KX(Q) + XWC(Q); |
| YWC(V) ← X*IY(Q) + Y*JY(Q) + Z*KZ(Q) + YWC(Q); |
| ZWC(V) ← X*IZ(Q) + Y*JZ(Q) + Z*KZ(Q) + ZWC(Q); |
---------------------------------------------------------------------
HOMOGENEOUS COORDINATES (LACK OF...)
The interpretation of frame nodes can be given in the
four by four notation of homogeneous coordinates.
7.0 IMAGE FORMING ROUTINES.
SAIL: GEODPY; GEOMED's display refresh.
SHOW1(window,glass); Display all edges.
SHOW2(window,glass); Display visible edges only.
SHOW3(window,glass); Display all visible faces.
LISP: (GEODPY) GEOMED's display refresh.
(SHOW1 window glass) Display all edges.
(SHOW2 window glass) Display visible edges only.
(SHOW3 window glass) Display all visible faces.
8.0 ARITHMETIC AND DISPLAY ROUTINES.
SQRT LOG SIN COS ATAN ATAN2 ASIN ACOS PI
DPYSET DPYBIG DPYBRT DPYSST
AVECT AIVECT RVECT RIVECT DPYOUT
The arithmetic and display routines are embedded in GEOMED so
that the typical user should not require SAITRG or DISPLY or any of
their equivalents. The next paragraph is a short explanation of the
display functions.
The CRT display screens are refreshed by a special purpose
display computer which executes a display file from core memory. With
the exception of DPYSET and DPYOUT; all of the diaplay subroutines
put display code into the display file. The display screen has 1024
by 1024 visible addressible positions with the origin in the center
of the screen, the positive X-axis to the right and the positive
Y-axis upwards. Thus display coordinates may range from -512 to +511;
9.0 Description of GEOMED Source Code.
The overall structure of GEOMED is determined by the urge to
have approximately one subroutine per page of source code. The
subroutine calling conventions are SAIL like; accumulator 17 (octal)
is named "P" and is used as a pushdown list for arguments and return
addresses. The subroutine calling sequence goes: PUSH P,ARG↔ PUSH
P,ARG↔ ... PUSHJ P,SUBR and a subroutine return must fix up the stack
SUB P,[XWD N+1,N+1] and JRST @N+1(P).
The somewhat unusal appearance of GEOMED code arises from the
use of FAIL assembler macros to implement ALGOL like subroutine
notation and Knuth like datum/link notation; and from the use of
double-arrow, "↔", to pack several machine instructions ito a line of
text and the use of seven alternate PDP-10 mnemonics.
The seven alternate PDP-10 mnemonics are LAC, DAC, CAR, CDR,
DIP, DAP and GO for MOVE, MOVEM, HLRZ, HRRZ, HRLM, HRRM and JRST
respectively. The LAC, DAC, DIP, DAP come from PDP-1 nomensclature
and are shorter and more pronoucible than their PDP-10 equivalents.
The CAR and CDR are from LISP which got them from the IBM-709. The
GO comes from ALGOL and is shorter and more descriptive than JRST.
The PDP-10 op code names sacrifice pronoucibility for systematic
nomensclature; and although I once proposed having alternate concise
euphonious names for the most frequently used operations; the idea
was quite unpopular and so I have abandoned it for all except the
above seven mnemonics.